package 其他.找出3位偶数2094;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 从给定的数字数组中找出所有可能的三位偶数
     * 此方法首先统计每个数字出现的次数，然后使用深度优先搜索（DFS）来组合这些数字
     * 以形成所有可能的三位偶数
     *
     * @param digits 给定的数字数组
     * @return 所有可能的三位偶数数组
     */
    public int[] findEvenNumbers(int[] digits) {
        // 统计每个数字出现的次数
        int[] cnt = new int[10];
        for (int i = 0; i < digits.length; i++) {
            cnt[digits[i]]++;
        }

        // 存储最终的答案
        List<Integer> ans = new ArrayList<>();
        // 调用深度优先搜索函数
        dfs(0, 0, cnt, ans);
        // 将答案转换为数组并返回
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 深度优先搜索（DFS）函数，用于生成所有可能的三位偶数
     *
     * @param cur 当前处理的数字位数
     * @param num 当前已经生成的数字
     * @param cnt 数字出现次数的统计数组
     * @param ans 存储最终答案的列表
     */
    private void dfs(int cur, int num, int[] cnt, List<Integer> ans) {
        // 如果已经生成了一个三位数，则将其添加到答案列表中
        if (cur == 3) {
            ans.add(num);
            return;
        }
        // 尝试在每个数字位置上放置一个有效的数字
        for (int i = 0; i < 10; i++) {
            // 检查当前数字是否可用，并根据当前处理的数字位数施加特定条件
            if (cnt[i] > 0 && (cur == 0 && i > 0 || cur == 1 || cur == 2 && i % 2 == 0)) {
                // 使用当前数字，递归调用DFS
                cnt[i]--;
                dfs(cur + 1, num * 10 + i, cnt, ans);
                // 回溯，撤销之前的选择
                cnt[i]++;
            }
        }
    }

}
